λ¬Έμ
μ΄λ² κ°μνκΈ°μ 'λ¬Έμ ν΄κ²°' κ°μλ₯Ό μ μ²ν νμλ€μ ν νλ‘μ νΈλ₯Ό μνν΄μΌ νλ€. νλ‘μ νΈ νμ μμλ μ νμ΄ μλ€. μ¬μ§μ΄ λͺ¨λ νμλ€μ΄ λμΌν νμ νμμΈ κ²½μ°μ κ°μ΄ ν νλ§ μμ μλ μλ€. νλ‘μ νΈ νμ ꡬμ±νκΈ° μν΄, λͺ¨λ νμλ€μ νλ‘μ νΈλ₯Ό ν¨κ»νκ³ μΆμ νμμ μ νν΄μΌ νλ€. (λ¨, λ¨ ν λͺ λ§ μ νν μ μλ€.) νΌμ νκ³ μΆμ΄νλ νμμ μκΈ° μμ μ μ ννλ κ²λ κ°λ₯νλ€.
νμλ€μ΄(s1, s2, ..., sr)μ΄λΌ ν λ, r=1μ΄κ³ s1μ΄ s1μ μ ννλ κ²½μ°λ, s1μ΄ s2λ₯Ό μ ννκ³ , s2κ° s3λ₯Ό μ ννκ³ ,..., sr-1μ΄ srμ μ ννκ³ , srμ΄ s1μ μ ννλ κ²½μ°μλ§ ν νμ΄ λ μ μλ€.
μ΄λ νλ‘μ νΈ νμλ μνμ§ μλ νμλ€μ μλ₯Ό κ³μ°νλ νλ‘κ·Έλ¨μ μμ±νλΌ.
μ λ ₯
- 첫째 μ€μ ν μ€νΈ μΌμ΄μ€μ κ°μ Tκ° μ£Όμ΄μ§λ€. κ° ν μ€νΈ μΌμ΄μ€μ 첫 μ€μλ νμμ μκ° μ μ n (2 β€ n β€ 100,000)μΌλ‘ μ£Όμ΄μ§λ€. κ° ν μ€νΈ μΌμ΄μ€μ λμ§Έ μ€μλ μ νλ νμλ€μ λ²νΈκ° μ£Όμ΄μ§λ€. (λͺ¨λ νμλ€μ 1λΆν° nκΉμ§ λ²νΈκ° λΆμ¬λλ€.)
μΆλ ₯
- κ° ν μ€νΈ μΌμ΄μ€λ§λ€ ν μ€μ μΆλ ₯νκ³ , κ° μ€μλ νλ‘μ νΈ νμ μνμ§ λͺ»ν νμλ€μ μλ₯Ό λνλ΄λ©΄ λλ€.
π Logic
class Graph {
final int[] graph;
int[] discovered;
boolean[] fin;
int answer = 0;
int graph_size;
public Graph(int size) {
graph_size = size + 1;
this.graph = new int[graph_size];
discovered = new int[graph_size];
fin = new boolean[graph_size];
}
}
- κ·Έλνμ μ 보λ₯Ό μ μ₯νκΈ° μν ν΄λμ€
public void search(int node) {
if (discovered[node] == 1) return;
discovered[node] = 1;
int next = graph[node];
if (discovered[next] == 0) search(graph[node]);
else {
if (!fin[next]) {
answer++;
for (int i=next; i!=node; i=graph[i]) {
answer++;
}
}
}
fin[node] = true;
}
- λ€μ λ°©λ¬Έν μ μ μ΄ λ°©λ¬Ένμ§ μμ κ²½μ°λ
search()λ‘ DFS μν -
λ€μ μ μ μ μ΄λ―Έ λ°©λ¬Έν κ²½μ°,
fin[next]λ‘ μ΄λ―Έ μ¬μ΄ν΄μ΄ νμ±λ μ μ μΈμ§ νμΈ- κ·Έλ μ§ μμ κ²½μ°, λ€μ ν΄λΉ μ μ μΌλ‘ λμμ€κΈ° μ κΉμ§ ν΄λΉ μ μ κ³Ό μ°κ²°λ μ μ μ μλ₯Ό μΉ΄μ΄νΈ
- μΉ΄μ΄νΈμ ν©μ΄ κ³§ νμ μ΄λ£¨λ νμλ€μ΄λ―λ‘, μ 체 νμ - λμ μΉ΄μ΄νΈκ° μ λ΅
π CODE
μ½λ 보기/μ κΈ°π«
import java.util.*;
class Graph {
final int[] graph;
int[] discovered;
boolean[] fin;
int answer = 0;
int graph_size;
public Graph(int size) {
graph_size = size + 1;
this.graph = new int[graph_size];
discovered = new int[graph_size];
fin = new boolean[graph_size];
}
public void AddElement(int x, int y) {
graph[x] = y;
}
public int solution() {
for (int i=1; i < graph_size; i++) this.search(i);
return graph_size - 1 - this.answer;
}
public void search(int node) {
if (discovered[node] == 1) return;
discovered[node] = 1;
int next = graph[node];
if (discovered[next] == 0) search(graph[node]);
else {
if (!fin[next]) {
// λ€μ κ° μ μ μ΄ λ°©λ¬Έμ νμΌλ μμ§ λλμ§ μμ, μ¦ μ¬μ΄ν΄μ΄ μμ±λμ§ μμ μν
answer++;
for (int i=next; i!=node; i=graph[i]) {
answer++;
}
}
}
fin[node] = true;
}
}
public class Main {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int T = sc.nextInt();
while (T > 0) {
int size = sc.nextInt();
Graph g = new Graph(size);
for (int i = 1; i <= size; i++) {
int tmp = sc.nextInt();
g.AddElement(i, tmp);
}
System.out.println(g.solution());
T-=1;
}
sc.close();
}
}
βοΈ Review
- κ²°κ΅μ "μ¬μ΄ν΄μ μ°ΎμμΌ νλ€" λΌλ λ Όλ¦¬λ λ§μμ§λ§, μ΅μ νλ₯Ό ν΄λ΄μ§ λͺ»ν΄ μκ° μ΄κ³Όλ₯Ό νΌν μ μμλ€.
- μ΄μ λΆν°λ ν루μ 1λ¬Έμ λ νμ΄μΌνκΈ° λλ¬Έμ λ무 μκ°μ μ‘μ λ¨Ήμ§ μμΌλ €κ³ νμ΄λ₯Ό μ°Έκ³ νλ€.
π μΆμ²
Baekjoon : https://www.acmicpc.net/problem/9466